struct Bridge {
    char ch;
    Bridge* next = nullptr;
    bool star = false;

    Bridge(char ch) : ch(ch), star(false), next(nullptr) {}
};

class Solution {
public:
    bool reCompare(char si, char pi);
    bool isMatch(string s, string p);
    template <typename T>
    Bridge *compile(T, T);

    template <typename T>
    bool match(Bridge *, T begin, T end);

    bool emptyEnd(Bridge* bridge);

    void debug(Bridge *bridge);
};



bool Solution::isMatch(string s, string p) {
    auto temp = compile(p.begin(), p.end());
//    debug(temp);
    return match(temp, s.begin(), s.end());
}



bool Solution::reCompare(char si, char pi) {
    if (pi == '.') {
        return true;
    }
    return pi == si;
}

template <typename T>
Bridge *Solution::compile(T begin, T end) {
    if (begin == end) {
        return nullptr;
    }
    auto *bridge = new Bridge(*begin);
    begin ++;
    if (*begin == '*') {
        bridge->star = true;
        begin++;
    }
    bridge->next = compile(begin, end);
    return bridge;
}

template<typename T>
bool Solution::match(Bridge *bridge, T begin, T end) {
    bool res = false;
    if (bridge == nullptr) {
//        cout << "end: " <<  begin.base() << endl;
        return begin == end;
    }
    if (begin == end) {
//        cout << "empty?";
        return emptyEnd(bridge);
    }
    // match this one
//    cout << *begin << bridge->ch << '\n';
//    cout << "BASE: " << begin.base() << '\n';
//    cout << "DEBUG:";
//    debug(bridge);
//    cout << '\n';
    if (bridge -> star) { // 选择是否跳过此位
        res = match(bridge->next, begin, end);
    }
    if (!reCompare(*begin, bridge->ch)) { // 比较与此位是否相同
        return res;
    }
    begin++; // 相同比较下一位
    if (bridge -> star) {
        res = match(bridge, begin, end) || res;
        if (res) return true;
    }
//    cout << "next" << '\n';
    return match(bridge -> next, begin, end) || res;
}

bool Solution::emptyEnd(Bridge *bridge) {
    if (bridge == nullptr) return true;
    if (bridge->star) {
        return emptyEnd(bridge->next);
    }
    return false;
}

void Solution::debug(Bridge *bridge) {
    if (bridge == nullptr) {
        return;
    }
    cout << bridge->ch;
    if (bridge->star) {
        cout << '*';
    }
    debug(bridge->next);
}